#pragma once

#include <def.h>
#include <memory.h>

typedef struct bst_node bst_node_t;

struct bst_node {
	struct bst_node* left_pn;
	struct bst_node* right_pn;
};

typedef iword_s cmp_ft(const void* data1_p, const void* data2_p);

typedef enum {
	BBST_SUCCESS = 0,
	BBST_DATA_EXIST,
	BBST_DATA_NOT_EXIST,
	BBST_MEM_ALLOC_FAIL,
} bbst_errno_s;

typedef struct bst bst_t;

typedef bbst_errno_s bbst_add_ft(bst_t* bst_p, const void* data_p);

typedef bbst_errno_s bbst_delete_ft(bst_t* bst_p, const void* data_p);

struct bst {
	bst_node_t* root_pn;
	bbst_add_ft* add_f;
	bbst_delete_ft* delete_f;
	u32_s data_offset;

	u32_s data_size;
	cmp_ft* cmp_f;
};

typedef struct {
	bst_node_t** node_link_pnp;
	bst_node_t* node_pn;
} bst_link_t;

static inline const void* bst_get_cdata_by_offset_p(const bst_node_t* node_p,
						    uword_s offset) {
	const u8_s* p = (const u8_s*)node_p;
	return p + offset;
}

static inline void* bst_get_data_by_offset_p(bst_node_t* node_p,
					     uword_s offset) {
	u8_s* p = (u8_s*)node_p;
	return p + offset;
}

static inline void* bst_get_data_p(bst_t* bst_p, bst_node_t* node_p) {
	return bst_get_data_by_offset_p(node_p, bst_p->data_offset);
}

static inline void bst_cpy_node_data(bst_t* bst_p, bst_node_t* node_p,
				     const void* data_p) {
	void* dst_data_p = bst_get_data_p(bst_p, node_p);
	memcpy(dst_data_p, data_p, bst_p->data_size);
}

bst_link_t bst_search_link(bst_t* bst_p, const void* data_p,
			   bst_link_t** write_node_pp,
			   const bst_link_t* endn_p);

constexpr uword_s MAX_HEIGHT = (sizeof(uword_s) << 4);

static inline bool_word_s bbst_search(bst_t* bst_p, const void* data_p) {
	bst_link_t space_a[MAX_HEIGHT];
	bst_link_t* space_p = space_a;
	bst_link_t result =
		bst_search_link(bst_p, data_p, &space_p, space_a + MAX_HEIGHT);
	return (result.node_pn != nullptr);
}

typedef void deal_bst_node_ft(const bst_node_t* node_p);

void bst_middle_iterate(const bst_t* bst_p, deal_bst_node_ft deal_f);

void bst_front_iterate(const bst_t* bst_p, deal_bst_node_ft deal_f);
